package org.aplombh.java.leetcode.all;

public class _4寻找两个正序数组的中位数 {
    public static void main(String[] args) {
        System.out.println(new Solution4_1().findMedianSortedArrays(new int[]{}, new int[]{1}));
    }
}

class Solution4_1 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int mid = (nums1.length + nums2.length + 1) / 2;
        int p = (nums1.length + nums2.length) % 2;
        float sum = 0;
        int i = 0, j = 0, k = 0, u = 0;

        for (; i < nums1.length && j < nums2.length; k++) {
            if (nums1[i] < nums2[j]) {
                u = nums1[i];
                i++;
            } else {
                u = nums2[j];
                j++;
            }
            if (k == mid - 1) {
                if (p == 1) {
                    return u;
                } else {
                    sum = u;
                }
            }
            if (k == mid) {
                return (sum + u) / 2;
            }
        }

        while (i < nums1.length) {
            u = nums1[i];
            if (k == mid - 1) {
                if (p == 1) {
                    return u;
                } else {
                    sum = u;
                }
            }
            if (k == mid) {
                return (sum + u) / 2;
            }
            i++;
            k++;
        }

        while (j < nums2.length) {
            u = nums2[j];
            if (k == mid - 1) {
                if (p == 1) {
                    return u;
                } else {
                    sum = u;
                }
            }
            if (k == mid) {
                return (sum + u) / 2;
            }
            j++;
            k++;
        }
        return u;
    }
}

// TODO
class Solution4_2 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int n = nums1.length;
        int m = nums2.length;

        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;

        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {

        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;

        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
}